#define _CRT_SECURE_NO_WARNINGS 1

#include <cstddef>
class PalindromeList {
public:
    struct ListNode* findmid(struct ListNode* cur)
    {
        if (cur == NULL)
        {
            return NULL;
        }
        ListNode* fast = cur;
        ListNode* low = cur;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            low = low->next;
        }
        return low;
    }

    struct ListNode* reverse(struct ListNode* head)
    {
        if (head == NULL)
        {
            return NULL;
        }
        ListNode* l1 = NULL;
        ListNode* l2 = head;
        ListNode* l3 = head->next;
        while (l2)
        {

            l2->next = l1;
            l1 = l2;
            l2 = l3;
            if (l3)
            {
                l3 = l3->next;
            }
        }
        return l1;
    }

    bool chkPalindrome(struct ListNode* A) {
        // write code here

        struct ListNode* mid = findmid(A);
        struct ListNode* B = reverse(mid);
        while (A && B)
        {
            if (A->val != B->val)
            {
                return false;
            }
            A = A->next;
            B = B->next;
        }
        return true;
    }
};



typedef struct ListNode ListNode;

int kthToLast(struct ListNode* head, int k) {

    ListNode* fast = head;

    ListNode* low = head;

    while (k--)

    {

        fast = fast->next;

    }

    while (fast)

    {

        fast = fast->next;

        low = low->next;

    }

    return low->val;

}